1. Field of the Invention
This invention is generally related to computer bus transactions, and more particularly to techniques for avoiding livelock when performing a relatively long stream of transactions across a bridge.
2. Description of Related Art
Peripheral devices such as disk controllers or network interface cards often generate a long stream of read or write transactions. The transactions are often directed at a main memory of the computer system. In certain architectures, the transactions must cross a bridge between a system bus to which the peripheral devices are coupled and the memory. The bridge has an inbound pipe for temporarily holding the data and request packets of multiple transactions before they are forwarded to the memory.
Sometimes the pipe becomes full before the stream can be completed. This may occur because the depth of the pipe is relatively small with respect to the number of transactions in the stream, and/or because the memory is relatively slow in emptying the pipe. When this happens, the peripheral device is refused access to the bridge and its inbound pipe. According to some bus arbitration protocols, the device must then relinquish the system bus to give a different device or agent a chance to own the bus. This is known as fair arbitration.
In certain situations, the pipe may still be full when a second agent is granted ownership of the bus. Thus, if the second agent also needs to access the pipe, then the bridge will refuse access. As required by fair arbitration, the second agent must now relinquish the bus so that other agents may then be granted ownership of the bus.
Eventually, the first agent being the peripheral device regains ownership of the bus. By now, however, assume that the pipe has emptied some, such that the first agent can resume its transaction stream. But since the stream is relatively long, the pipe once again becomes full and the first agent must relinquish the bus. Although arbitration may now move to the second agent, the pipe may still be full and the bridge must again refuse access to the second agent. The cycle of the previous paragraph may repeat several times, thereby starving the second agent while allowing the first agent to progress with its long transaction stream.
The undesirable condition described above is known as livelock, where the second agent cannot progress even though it is granted ownership of the bus. In addition to reducing the performance of the second agent, livelock wastes valuable bus cycles when the second agent requests and is granted the bus only to be refused access to the bridge, with no data being transferred over the bus.
One possible solution for dealing with the livelock problem is configuring the bridge with a larger pipe so that the entire stream can be accepted by the bridge. This may be prohibitively expensive, because the transaction streams described above may be very long such that no practical pipe could hold the entire stream. Alternatively, the memory and peripheral devices may be reconfigured to split the transaction stream into smaller portions, allowing ownership of the bus to pass to another agent between portions. This solution, however, requires altering many different types of memory and peripheral devices, all of which may be developed by different manufacturers and according to different standards. This may also undesirably increase the overall cost of ownership of the system by requiring many components of the system to be redesigned.
Therefore, there is a need to remedy the livelock condition described above using a relatively low-cost technique that does not require extensive reconfiguration of existing peripheral devices.